Nondeterministic algorithm

In computer science, a nondeterministic algorithm is an algorithm that can exhibit different behaviors on different runs, as opposed to a deterministic algorithm. There are several ways an algorithm may behave differently from run to run. A concurrent algorithm can perform differently on different runs due to a race condition. A probabalistic algorithm's behaviors depends on a random number generator. An algorithm that solves a problem in nondeterministic polynomial time can run in polynomial time or exponential time depending on the choices it makes during execution.

Contents

Use

Often in computational theory, the term "algorithm" refers to a deterministic algorithm. A nondeterministic algorithm is different from its more familiar deterministic counterpart in its ability to arrive at outcomes using various routes. If a deterministic algorithm represents a single path from an input to an outcome, a nondeterministic algorithm represents a single path stemming into many paths, some of which may arrive at the same output and some of which may arrive at unique outputs. This property is captured mathematically in "nondeterministic" models of computation such as the nondeterministic finite automaton.

In algorithm design, nondeterministic algorithms are often used when the problem solved by the algorithm inherently allows multiple outcomes (or when there is a single outcome with multiple paths by which the outcome may be discovered, each equally preferable). Crucially, every outcome the nondeterministic algorithm produces is valid, regardless of which choices the algorithm makes while running.

In computational complexity theory, nondeterministic algorithms are ones that, at every possible step, can allow for multiple continuations (imagine a man walking down a path in a forest and, every time he steps further, he must pick which fork in the road he wishes to take). These algorithms do not arrive at a solution for every possible computational path; however, they are guaranteed to arrive at a correct solution for some path (i.e., the man walking through the forest may only find his cabin if he picks some combination of "correct" paths). The choices can be interpreted as guesses in a search process.

A large number of problems can be conceptualized through nondeterministic algorithms, including the most famous unresolved question in computing theory, P = NP.

Implementing nondeterministic algorithms with deterministic ones

One way to simulate a nondeterministic algorithm N using a deterministic algorithm D is to treat sets of states of N as states of D. This means that D simultaneously traces all the possible execution paths of N (see powerset construction for this technique in use for finite automata).

Another is randomization, which consists of letting all choices be determined by a random number generator. The result is called a probabilistic deterministic algorithm.

Examples

Example 1: Merge sort

Suppose we have a finite collection of things (say, 300 student exams) that we need to sort (say, by student number).

One algorithm to do this (called merge sort):

Items can only be uniquely sorted if the sorting criterion chosen always defines a total order; e.g. student numbers are expected to be unique, but if we sort exams by name and two students happen to have the same name, the order in which their exams get sorted is left undefined. In such cases, merge sort will always arrive at one of the possible valid orderings, but which one is left unspecified—hence it is nondeterministic.

Example 2: Spanning tree

The input is an undirected connected graph. An undirected graph is a set of nodes that may or may not be pairwise connected with edges. A subgraph of a graph consists of a subset of its nodes and/or edges. A graph connects two nodes if we can walk over its edges from one to the other. A path in a graph is a minimal subgraph connecting two of its nodes. A graph is connected if it connects all of its nodes.

The algorithm: while an edge can be removed such that the graph is still connected, remove such an edge.

The output: a spanning tree, that is, a subgraph that is a tree connecting all the nodes.

Every graph (that is connected and not a tree) has multiple spanning trees, so we once again have an example where the problem itself allows multiple possible outcomes, and the algorithm chosen can arrive at any one of them, but will never arrive at something else.

This is, again, an algorithm that always arrives at a correct solution to the problem.

Example 3: Primality testing

The problem: given a natural number n larger than two, determine whether it is prime.

A nondeterministic algorithm for this problem is the following based on Fermat's little theorem:

  1. Repeat thirty times:
    1. Pick a random integer a such that 2 ≤ a ≤ n-1.
    2. If a^{n-1}\neq 1 \pmod n, return answer composite
  2. Return answer probably prime.

If this algorithm returns the answer composite then the number is certainly not prime. If the algorithm returns the answer probably prime then there is a high probability that the number is prime, but a slight chance that it is composite. This is an example of a probabilistic nondeterministic algorithm, because it will not always return the same result given a particular input.[1]

References

Cormen et al. Introduction to Algorithms, Third Edition. ISBN 978-0-262-03384-8. 
"nondeterministic algorithm". NIST. http://xlinux.nist.gov/dads/HTML/nondetermAlgo.html. 
"Non-deterministic Algorithms". http://cs.nyu.edu/courses/spring03/G22.2560-001/nondet.html. 

See also

References

  1. ^ "Primality Testing : Non-deterministic Algorithms". TopCoder. http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=primalityTesting. Retrieved August 21, 2011.